IOI2019 景点划分

pufanyi

题解

发布于：Oct 3, 2021

给一张 $n\,(3\le n\le 10^5)$ 个点 $m\,(2\le m\le 2\times 10^5)$ 条边的无向连通图，以及三个正整数 $a,b,c$，保证 $a+b+c=n$。你需要对每个点染成三种颜色中的一种，使得这三种颜色的点的个数分别为 $a,b,c$，且有两种颜色的点构成两个联、连通块。可能无解。

我们先考虑我们这两个连通块的大小应该为多少。我们不妨令 $a\le b\le c$，那么我们发现其实只要让 $a$ 和 $b$ 是连通块即可。因为如果是 $c$ 是连通块，那么我们显然可以通过删掉部分节点的方式将其的大小缩小。

考虑到这一点，如果这是一棵树的话，那算法就简单了。我们考虑枚举一条边，如果边两边的 size 分别大于了 $a$ 和 $b$，那就 YES 了。如果找不到的话，那显然就是 NO。

然后我们考虑图的情况，其实就是在这棵树上加了几条边。考虑到我们考虑这棵树是这张无向图的 dfs 树，这样这些新加进去的边就一定是返祖边，而不会存在横叉边的情况。我们先忽略这条边，如果找到了一边大于 $a$ 一边大于 $b$，那一定 YES。我们考虑找不到的情况，这时候我们就可以用那几条返祖边进行调整。一种比较直接的调整方法是，考虑 $x$ 与 $f_x$（$x$ 父亲）的那条边，那我们可以将 $x$ 子树中，存在返祖边为 $x$ 祖先的那些子树加入到 $f_x$ 所在的那个集合中。也就是用减少 $x$ 所在连通块大小的代价换取 $f_x$ 所在连通块大小的增加。让我们考虑对于一个 $x$，令 $s_x$ 表示节点 $x$ 的大小。由于我们调整的目的是为了让 $f_x$ 所在连通块更大，所以我们考虑让 $x$ 所在连通块不经过调整不能再小了，也就是 $s_x\ge a$ 但对于 $x$ 的任意一个儿子 $t$，都有 $s_t<a$。然后我们考虑进行调整。我们最终一定能找到一个临界，也就是不能继续调整了。这个时候有两种情况，第一种情况是，虽然还是有未加入 $f_x$ 所在连通块的存在与之有返祖边联通的子树 $t$，但如果加入该子树，那么 $x$ 所在连通块大小就小于 $a$ 了，考虑到此时 $x$ 所在连通块大小为 $u$，子树 $t$ 大小为 $v$，我们有 $\begin{cases}u\ge a\\u - v < a\\v < a\end{cases}$，也即 $a\le u < 2a$ 那么我们考虑 $f_x$ 所在连通块的大小：$n-u=a+b+c-u>a+b+c-2a=b+(c-a)\ge b$。也就是说这种情况一定是 YES 的。然后我们考虑第二种情况，就是已经没有子树有可用的返祖边了，那这时候如果 $f_x$ 所在连通块大小仍然小于 $b$ 的话，那对于这个点，一定是不可能的了。那么，我们只要继续考虑其他的同样满足 $s_x\ge a$ 且对于 $x$ 的任意儿子 $t$ 都有 $s_t<a$ 的所有 $x$ 即可。如果都不满足条件，那显然答案是 NO。这样复杂度 $\mathcal{O}(n)$。

更新于：Dec 26, 2023

构造

图论